COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\rm
C00005 ENDMK
C⊗;
\rm
\magnification=\magstephalf

\noindent
4. Convert the $gsm$ to the form where inputs and outputs are at most one
character. Construct a $NPDA$ whose states and connections are the same as
those of the $gsm$, except:

\vskip .125in

(1) If $\quad i$ \hskip .25in $↑{(/x}$ \hskip .25in $j\quad$ in the $gsm$, then

\vskip .125in

$\quad i$ \hskip .5in Push 1 \hskip .5in Read \hskip .25in $↑x$ 
\hskip .25in $j\quad$ in the $NPDA$

\vskip .125in

\hskip 1.75in $↑{\rm other}$\hskip .25in Reject

\vskip .125in

(2) If $\quad i$ \hskip .25in $↑{)/x}$ \hskip .25in $j\quad$ in the $gsm$, then

\vskip .125in

$\quad i$ \hskip .5in Empty?\hskip .5in No\hskip .5in Pop\hskip .25in $↑1$
\hskip .5in Read\hskip .25in $↑x$\hskip .25in $j\quad$ in the $NPDA$

\vskip .125in

\hskip 1in Yes\hskip .25in Reject \hskip 1.75in $↑{\rm other}$\hskip .25in Reject

\vskip .125in

(3) If $\quad i$ \hskip .25in $↑{ε/x}$\hskip .25in $j\quad$ in the $gsm$, then

\vskip .125in

$\quad i$\hskip .5in Read \hskip .25in $↑x$\hskip .5in $j\quad$ in the $NPDA$

\vskip .125in

\hskip .75in $↑{\rm other}$\hskip .5in Reject

\vskip .125in

where the reads are omitted if $x=ε$. (The $NPDA$ accepts only if the stack is
empty.) The $NPDA$ accepts exactly the $gsm$'s transductions of the
one-parenthesis language, and since only one symbol goes on the stack, it is a
one-counter machine.

\vfil\end